package com.example.algorithm.kmp;

/**
 * 实现 strStr() 函数。
 *  给你两个字符串 haystack 和 needle ，请你在 haystack 字符串中找出 needle 字符串出现的第一个位置（下标从 0 开始）。
 *  如果不存在，则返回 -1 。
 *  说明：当 needle 是空字符串时，我们应当返回什么值呢？这是一个在面试中很好的问题。
 *  对于本题而言，当 needle 是空字符串时我们应当返回 0 。这与 C 语言的 strstr() 以及 Java 的 indexOf() 定义相符。
 *
 *  示例 1：
 * 输入：haystack = "hello", needle = "ll"
 * 输出：2
 *
 *  示例 2：
 * 输入：haystack = "aaaaa", needle = "bba"
 * 输出：-1
 *
 *  示例 3：
 * 输入：haystack = "", needle = ""
 * 输出：0
 *
 *  提示：
 *  0 <= haystack.length, needle.length <= 5 * 104
 *  haystack 和 needle 仅由小写英文字符组成
 */
public class Leetcode28_strStr {
    public static void main(String[] args) {
        String haystack = "hello";
        String needle = "ll";
//        haystack = "aaaaab"; needle = "ab";
//        haystack = "";needle = "";
//        haystack = "abcbcd"; needle = "cbcd";
        System.out.println(new Solution().strStr(haystack, needle));

    }

    static class Solution {

        private int strStr3(String haystack, String needle) {

            return 0;
        }

        /**
         * 解法二:KMP算法
         * 常用于在一个文本串S内查找一个模式串P 的首次出现位置
         *
         * 算法思路
         * 分析模式串特征，nexts[]保存模式串中前后缀最长重复子串长度
         * 每次回溯时，通过nexts[]找到前面匹配过的位置
         *
         * 模式串特征分析：当匹配不成功时找到最理想的模式串移动位置
         *   1. 该字符不匹配时，模式串下一次比对位置
         *   2. 该位置前的前缀、后缀 匹配的最大长度("前缀"指除了最后一个字符以外，一个字符串的全部头部组合；"后缀"指除了第一个字符以外，一个字符串的全部尾部组合)
         *   3. 第0个位置前面无字符存-1
         *
         * 遍历每一个字符计算next[]
         *   1 初始next[0]为-1
         *   2 双指针比对前缀k、后缀j
         *   3 相等，双指针都后移
         *     用前缀下标k填充next[j]
         *   4 不相等前缀k指针回溯
         *     回溯时利用已计算的next[k]
         *   5 前缀指针为-1则需要对双指针都后移，用前缀下标k填充next[j]
         *
         * @param haystack
         * @param needle
         * @return
         */
        private int strStr2(String haystack, String needle) {
            int n = haystack.length();
            int m = needle.length();
            if (m == 0)
                return 0;
            if (n < m)
                return -1;
            char[] chars = haystack.toCharArray();
            char[] pattern = needle.toCharArray();
            // 分析pattern得到 pattern的nexts数组
            int[] nexts = getNexts(pattern);

            int i = 0, j = 0;
            while (i < n && j < m) {
                if (chars[i] == pattern[j]) {
                    j++;
                    i++;
                } else { // 遇到不匹配的回溯到next[j]的位置
                    if (nexts[j] == -1) { // pattern字符串第一个就不匹配或者pattern的该位置没有真前/后缀时需要将j置0
                        i++;
                        j = 0;
                    } else {
                        j = nexts[j];
                    }
                }

                if (j == m) { // 匹配到了pattern的最后一个字符,说明完全匹配了
                    return i - j;
                }

            }
            return -1;
        }

        /**
         * 解法一:双指针法
         * 一个指针用于遍历haystack,一个用于遍历needle
         * @param haystack
         * @param needle
         * @return
         */
        private int strStr1(String haystack, String needle) {
            int n = haystack.length();
            int m = needle.length();
            if (m == 0)
                return 0;
            if (n < m)
                return -1;
            char[] chars = haystack.toCharArray();
            char[] pattern = needle.toCharArray();

            for (int i = 0; i < n; i++) {
                int t = i;
                if (n - i < m) return -1; // chars所剩长度 < pattern总长度 不需要再进行比较了,肯定不匹配
                for (int j = 0; j < m; j++) {
                    if (chars[t] == pattern[j]) {
                        t++;
                        if (j == m - 1) // pattern匹配到了最后一个字符,说明成功匹配
                            return t - m;
                    } else {
                        break;
                    }
                }
            }
            return -1;
        }

        private int[] getNexts(char[] pattern) {
            int[] nexts = new int[pattern.length];
            int j = 0;// 模式串下标 后缀
            int k = -1;// 模式串前缀下标 也是前后缀匹配的长度
            nexts[0] = -1;// 0位置前面没有字符了，所以默认存-1
            int len = pattern.length;
            while (j < len - 1) {//模式串下标未到达最后一个位置
                if (k == -1 || pattern[k] == pattern[j]) {
                    // 到达模式串开头或者匹配成功，则移动到下一位置
                    k++;// 模式串前缀下标移动到下一位置
                    j++;// 模式串移动到下一位置
                    nexts[j] = k;// 把当前k值存放到next数组中
                } else {// 不匹配时，需要对k进行回溯
                    k = nexts[k];// 使用next来找不匹配时的下一个移动位置
                }
            }
            return nexts;
        }

        public int strStr(String haystack, String needle) {
            return strStr2(haystack, needle);
        }
    }
}
